package tree.binary_tree.heap;

/**
 * 堆(大顶堆)的常见操作 插入数据，删除堆顶
 *
 * @author yeyangtao created at 11:41 2020/10/14
 */
public class MyHeap {
    private final int[] data;
    private final int size;
    private int currSize;

    public MyHeap(int capacity) {
        data = new int[capacity + 1];
        this.size = capacity;
        currSize = 0;
    }

    /**
     * 插入数据 自下往上堆化
     */
    public void insert(int a) {
        //堆满了
        if (currSize >= size) return;
        ++currSize;
        data[currSize] = a;
        int i = currSize;
        //自下往上堆化 当前与父节点比较、交换
        while (i / 2 > 0 && data[i] > data[i / 2]) {
            int temp = data[i];
            data[i] = data[i / 2];
            data[i / 2] = temp;
            i = i / 2;
        }
    }

    /**
     * 删除堆顶 自上而下堆化
     */
    public void deleteTop() {
        if (currSize <= 1) return;
        data[1] = data[currSize];
        //自上而下堆化
        int i = 1;
        while (true) {
            int maxPos = 1;
            if (i * 2 <= currSize && data[i] < data[i * 2]) maxPos = i * 2;
            if (i * 2 + 1 <= currSize && data[maxPos] < data[i * 2 + 1]) maxPos = i * 2 + 1;
            if (maxPos == i) break;

            //交换根节点i与子节点maxPos
            int temp = data[i];
            data[i] = data[maxPos];
            data[maxPos] = temp;

            i = maxPos;
        }
    }
}
